// @algorithm @lc id=1733 lang=cpp 
// @title maximum-number-of-visible-points


#define print(...)
// @test([[2,1],[2,2],[3,3]],90,[1,1])=3
// @test([[2,1],[2,2],[3,4],[1,1]],90,[1,1])=4
// @test([[1,0],[2,1]],13,[1,1])=1
class Solution {
public:
    int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {
        int sameCnt = 0;
        vector<double> polarDegrees;
        for (auto & point : points) {
            if (point[0] == location[0] && point[1] == location[1]) {
                sameCnt++;
                continue;
            }
            double degree = atan2(point[1] - location[1], point[0] - location[0]);
            polarDegrees.emplace_back(degree);
        }
        sort(polarDegrees.begin(), polarDegrees.end());

        int m = polarDegrees.size();
        for (int i = 0; i < m; ++i) {
            polarDegrees.emplace_back(polarDegrees[i] + 2 * M_PI);
        }

        int maxCnt = 0; 
        double degree = angle * M_PI / 180;
        for (int i = 0; i < m; ++i) {
            auto it = upper_bound(polarDegrees.begin() + i, polarDegrees.end(), polarDegrees[i] + degree);
            int curr = it - polarDegrees.begin() - i;
            maxCnt = max(maxCnt, curr);
        }
        return maxCnt + sameCnt;
    }
};

/*作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-number-of-visible-points/solution/you-xiao-ke-jian-dian-de-zui-da-shu-mu-b-r1qz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/